home *** CD-ROM | disk | FTP | other *** search
/ Oh!X 2001 Spring / Oh!X 2001 Spring Special CD-ROM (Japan).7z / Oh!X 2001 Spring Special CD-ROM (Japan) (Track 1).bin / PUZZLE / puz01 / keiro.c < prev    next >
C/C++ Source or Header  |  2000-02-20  |  1KB  |  72 lines
  1. /*
  2.  * keiro.c : 経路の探索
  3.  *
  4.  */
  5. /*
  6.         1       3       5
  7.         Ｂ------Ｄ------Ｆ
  8.       ／│      │          
  9.   0 Ａ  │      │          
  10.       ＼│      │          
  11.         Ｃ------Ｅ------Ｇ
  12.         2       4       6
  13.  
  14.          経路図
  15.  
  16. */
  17. #include <stdio.h>
  18. #include <stdlib.h>
  19. #include <string.h>
  20.  
  21. #define NODE 7
  22.  
  23. /* 隣接リスト */
  24. const char adjacent[NODE][4] = {
  25.   1,  2, -1, -1,    /* A */
  26.   0,  2,  3, -1,    /* B */
  27.   0,  1,  4, -1,    /* C */
  28.   1,  4,  5, -1,    /* D */
  29.   2,  3,  6, -1,    /* E */
  30.   3, -1, -1, -1,    /* F */
  31.   4, -1, -1, -1,    /* G */
  32. };
  33.  
  34. /* 経路 */
  35. char path[NODE];
  36.  
  37. /* 経路の表示 */
  38. void print_path( int len )
  39. {
  40.   int i;
  41.   for( i = 0; i <= len; i++ ){
  42.     printf("%c ", path[i] + 'A' );
  43.   }
  44.   printf("\n");
  45. }
  46.  
  47. /* 経路の探索 */
  48. void search( int len, int node, int goal )
  49. {
  50.   path[len] = node;
  51.   if( node == goal ){
  52.     /* 到達した */
  53.     print_path( len );
  54.   } else {
  55.     int n, i;
  56.     for( i = 0; (n = adjacent[node][i]) != -1; i++ ){
  57.       if( memchr( path, n, len ) == NULL ){
  58.     search( len + 1, n, goal );
  59.       }
  60.     }
  61.   }
  62. }
  63.  
  64. int main()
  65. {
  66.   /* A -> G */
  67.   search( 0, 0, 6 );
  68.   return 0;
  69. }
  70.  
  71. /* end of file */
  72.